package LRU;


import java.util.HashMap;
import java.util.LinkedList;

//基于双向链表+HashMap的形式 使得查找和删除的效率都可以做到O(n)
//然后维护左右两端的指针，完成添加和淘汰，这里左淘汰 右添加
public class LRUCache {
    class Node{
        int val;
        Node pre;
        Node next;
        public Node(){}
        public Node(int val){
            this.val = val;
        }
    }
    private HashMap<Integer,Node> map ;
    private final int MaxLen;   //最大长度
    private int len ;   //实际长度
    Node first;
    Node last;
    public LRUCache(int len){  //实例化的时候需要制定最大长度
        map = new HashMap<>();
        MaxLen = len;
    }

    //1. 如果该数据存在，则删除对应的元素(其实本意是要将该数据移动到数组最后面，这里直接先删除，后面再添加)
    //2. 判断数组长度是否超过限制
    //3. 如果超过限制，则删除数组最前面的元素，即下标为0的元素
    //4. 将数据添加到数组最后面
    public void put(int key,int val){
        Node node=null;
        if (map.containsKey(key)){   //如果已经存在，则移动位置到最后面，并更新值
            node = map.get(key);
            node.val = val;
        }else{
            node = new Node(val);
            map.put(key,node);
            len++;
        }
        moveToFirst(node);
    }

    //1. 如果该数据存在，则将该数据放到数组最后面，并返回val
    //2. 如果数据不存在，则返回-1

    public void moveToFirst(Node node){

    }

    public void moveToLast(Node node){

    }

}
